﻿#ifndef __STD_TRIE_TREE_H__
#define __STD_TRIE_TREE_H__
#include "stdTrieNode.h"
#include "ssTrieTreeDef.h"

namespace StarSeeker
{

	template<typename T_KEY, typename T_VALUE>
	class stdTrieTree
	{
	public:
		stdTrieTree();
		~stdTrieTree();
		stdTrieTree(const stdTrieTree& dic);
		void operator= (const stdTrieTree& dic);

		//查找
		stdTrieNode<T_KEY, T_VALUE>* Find(const T_KEY* arr, size_t len);
		//插入
		std::pair<stdTrieNode<T_KEY, T_VALUE>*, short> Insert(stdTrieNode<T_KEY, T_VALUE>* parent, T_KEY k, T_VALUE* val);
		std::pair<stdTrieNode<T_KEY, T_VALUE>*, short> Insert(const T_KEY* arr, size_t len, T_VALUE* val);
		//删除
		short Remove(stdTrieNode<T_KEY, T_VALUE>* node);
		short Remove(const T_KEY* arr, size_t len);
		//返回节点数
		size_t GetCount() { return m_count; }
		//清空树
		void Empty();
	private:
		//复制对象
		void CopyFrom(const stdTrieTree& dic);
		//遍历删除节点
		void RecursionEmpty(stdTrieNode<T_KEY, T_VALUE>* itr);
		//遍历复制
		void RecursionCopy(const stdTrieNode<T_KEY, T_VALUE>* itr, stdTrieNode<T_KEY, T_VALUE>* parent);
	private:
		stdTrieNode<T_KEY, T_VALUE>			m_root;
		size_t								m_count;
	};

	template<typename T_KEY, typename T_VALUE>
	inline stdTrieTree<T_KEY, T_VALUE>::stdTrieTree()
	{
		m_root.m_pOnwer = this;
		m_count = 0;
	}

	template<typename T_KEY, typename T_VALUE>
	inline stdTrieTree<T_KEY, T_VALUE>::~stdTrieTree()
	{
		Empty();
	}

	template<typename T_KEY, typename T_VALUE>
	inline stdTrieTree<T_KEY, T_VALUE>::stdTrieTree(const stdTrieTree & dic)
	{
		m_root.m_pOnwer = this;
		m_count = 0;
		CopyFrom(dic);
	}

	template<typename T_KEY, typename T_VALUE>
	void stdTrieTree<T_KEY, T_VALUE>::operator=(const stdTrieTree& dic)
	{
		Empty();
		CopyFrom(dic);
	}

	template<typename T_KEY, typename T_VALUE>
	inline stdTrieNode<T_KEY, T_VALUE> * stdTrieTree<T_KEY, T_VALUE>::Find(const T_KEY* arr, size_t len)
	{
		stdTrieNode<T_KEY, T_VALUE>* node = &m_root;
		for (size_t i = 0; i < len; i++)
		{
			typename std::map<T_KEY, stdTrieNode<T_KEY, T_VALUE>*>::iterator itr = node->m_children.find(arr[i]);
			if (itr == node->m_children.end())
			{
				return 0;
			}
			node = itr->second;
		}
		return node;
	}

	template<typename T_KEY, typename T_VALUE>
	inline std::pair<stdTrieNode<T_KEY, T_VALUE>*, short> stdTrieTree<T_KEY, T_VALUE>::Insert(stdTrieNode<T_KEY, T_VALUE>* parent, T_KEY k, T_VALUE * val)
	{
		if (parent && parent->m_pOnwer==this)
		{
			typename std::map<T_KEY, stdTrieNode<T_KEY, T_VALUE>*>::iterator itr = parent->m_children.find(k);
			if (itr != parent->m_children.end())
			{
				return std::pair<stdTrieNode<T_KEY, T_VALUE>*, short>(itr->second, SS_DICT_KEY_EXISTED);
			}
			stdTrieNode<T_KEY, T_VALUE>* newNode = new stdTrieNode<T_KEY, T_VALUE>;
			newNode->m_pParent = parent;
			newNode->m_pOnwer = this;
			newNode->m_key = k;
			newNode->m_pValue = val;
			std::pair<typename std::map<T_KEY, stdTrieNode<T_KEY, T_VALUE>*>::iterator, bool> ret = parent->m_children.insert(std::pair<T_KEY, stdTrieNode<T_KEY, T_VALUE>*>(k, newNode));
			if (ret.second)
			{
				++m_count;
				return std::pair<stdTrieNode<T_KEY, T_VALUE>*, short>(ret->first->second, SS_DICT_OK);
			}
			else
			{
				delete newNode;
				return std::pair<stdTrieNode<T_KEY, T_VALUE>*, short>(0, SS_DICT_CREATE_NODE_FAILED);
			}
		}
		return std::pair<stdTrieNode<T_KEY, T_VALUE>*, short>(0, SS_DICT_CREATE_NODE_FAILED);
	}

	template<typename T_KEY, typename T_VALUE>
	inline std::pair<stdTrieNode<T_KEY, T_VALUE>*, short> stdTrieTree<T_KEY, T_VALUE>::Insert(const T_KEY* arr, size_t len, T_VALUE* val)
	{
		if (arr == 0 || len == 0)
		{
			return std::pair<stdTrieNode<T_KEY, T_VALUE>*, short>(0, SS_DICT_KEY_ILLEGAL);
		}
		stdTrieNode<T_KEY, T_VALUE>* node = &m_root;
		for (size_t i = 0; i < len; i++)
		{
			typename std::map<T_KEY, stdTrieNode<T_KEY, T_VALUE>*>::iterator itr = node->m_children.find(arr[i]);
			if (itr == node->m_children.end())
			{
				stdTrieNode<T_KEY, T_VALUE>* newNode = new stdTrieNode<T_KEY, T_VALUE>;
				newNode->m_pParent = node;
				newNode->m_pOnwer = this;
				newNode->m_key = arr[i];
				if (i == len - 1)
					newNode->m_pValue = val;
				std::pair<typename std::map<T_KEY, stdTrieNode<T_KEY, T_VALUE>*>::iterator, bool> ret = node->m_children.insert(std::pair<T_KEY, stdTrieNode<T_KEY, T_VALUE>*>(arr[i], newNode));
				if (ret.second)
				{
					node = ret.first->second;
				}
				else
				{
					delete newNode;
					return std::pair<stdTrieNode<T_KEY, T_VALUE>*, short>(0, SS_DICT_CREATE_NODE_FAILED);
				}
			}
			else
			{
				node = itr->second;
				if (i == len - 1)
					return std::pair<stdTrieNode<T_KEY, T_VALUE>*, short>(node, SS_DICT_KEY_EXISTED);
			}
		}
		++m_count;
		return std::pair<stdTrieNode<T_KEY, T_VALUE>*, short>(node, SS_DICT_OK);
	}

	template<typename T_KEY, typename T_VALUE>
	short StarSeeker::stdTrieTree<T_KEY, T_VALUE>::Remove(stdTrieNode<T_KEY, T_VALUE>* node)
	{
		if (node == 0)
		{
			return SS_DICT_KEY_NOTEXISTED;
		}
		if (node->m_pOnwer != this)
		{
			return SS_DICT_DEL_ILLEGAL;
		}
		if (node->m_pParent == 0)
		{
			return SS_DICT_DEL_ILLEGAL;
		}
		if (node->m_children.empty())//叶节点
		{
			stdTrieNode<T_KEY, T_VALUE>* parent = node->m_pParent;
			while (node && parent)
			{
				if (node->m_pValue)
				{
					delete node->m_pValue;
					node->m_pValue = 0;
					node->m_pOnwer = 0;
				}
				parent->m_children.erase(node->m_key);
				delete node;
				node = parent;
				if (node)
				{
					parent = node->m_pParent;
				}
				if (!node->m_children.empty() || node->m_pValue)
				{
					break;
				}
			}
		}
		else
		{
			if (node->m_pValue)
			{
				delete node->m_pValue;
				node->m_pValue = 0;
			}
		}
		--m_count;
		return SS_DICT_OK;
	}

	template<typename T_KEY, typename T_VALUE>
	inline short stdTrieTree<T_KEY, T_VALUE>::Remove(const T_KEY* arr, size_t len)
	{
		stdTrieNode<T_KEY, T_VALUE>* node = Find(arr, len);
		return Remove(node);
	}

	template<typename T_KEY, typename T_VALUE>
	inline void stdTrieTree<T_KEY, T_VALUE>::Empty()
	{
		m_count = 0;
		RecursionEmpty(&m_root);
	}

	template<typename T_KEY, typename T_VALUE>
	inline void stdTrieTree<T_KEY, T_VALUE>::CopyFrom(const stdTrieTree & dic)
	{
		RecursionCopy(&dic.m_root, &m_root);
	}

	template<typename T_KEY, typename T_VALUE>
	inline void stdTrieTree<T_KEY, T_VALUE>::RecursionEmpty(stdTrieNode<T_KEY, T_VALUE>* itr)
	{
		if (itr)
		{
			if (!itr->m_children.empty())
			{
				for (typename std::map<T_KEY, stdTrieNode<T_KEY, T_VALUE>*>::iterator i = itr->m_children.begin(); i != itr->m_children.end(); ++i)
				{
					RecursionEmpty(i->second);
				}
				itr->m_children.clear();
			}
			if (itr->m_pValue)
			{
				delete itr->m_pValue;
				itr->m_pValue = 0;
			}
			if (itr->m_pParent)
			{
				itr->m_pOnwer = 0;
				delete itr;
			}
		}
	}

	template<typename T_KEY, typename T_VALUE>
	inline void stdTrieTree<T_KEY, T_VALUE>::RecursionCopy(const stdTrieNode<T_KEY, T_VALUE>* itr, stdTrieNode<T_KEY, T_VALUE>* parent)
	{
		if (itr)
		{
			T_VALUE* pValue = 0;
			if (itr->m_pValue)
			{
				pValue = new T_VALUE;
				*pValue = *itr->m_pValue;
			}
			Insert(parent, itr->m_key, pValue);
			if (!itr->m_children.empty())
			{
				for (typename std::map<T_KEY, stdTrieNode<T_KEY, T_VALUE>*>::iterator i = itr->m_children.begin(); i != itr->m_children.end(); ++i)
				{
					RecursionCopy(i->second, itr);
				}
			}
		}
	}
}
#endif
